The present invention relates to an instruction sequence optimizing method of a compiler for converting a source program into an assembly language which can be executed by a pipeline computer and, more particularly, to an instruction sequence optimizing method of a compiler for instruction sequences of the IF.about.THEN type and IF.about.THEN.about.ELSE type as targets.
The compiler which is known as a language processor converts a source program described by a programming language such as FORTRAN, COBOL, PL/I, or the like into an assembly language or a machine language which can be executed by a computer, thereby forming a target program. In such a compiler, at a stage after completion of the conversion and formation into an intermediate code, an optimizing process of the code is executed. By optimizing the code, the intermediate code can be converted into an instruction sequence which is executed by a minimum capacity and at a highest speed on the computer for executing the program, so that such a code optimization largely contributes to the improvement of the performance of the compiler.
Hitherto, for example, a program having steps 1 to 6 including a branch instruction shown in FIG. 1 is executed. FIG. 1 shows an example of the program of the IF.about.THEN type including a branch instruction which was converted by the conventional compiler. The program is shown by the assembly language. Numerical formula-like meanings, contents, and further a processing procedure are also shown as processing routes. In the assembly language, "%" shows a register. For instance, "%r10" denotes a register r10. "mov" denotes a moving instruction, "cmp" indicates a comparing instruction, "ble" an index indicative of a branch destination label, and "add" an adding instruction.
In FIG. 1, the comparing instruction "cmp" in step 3 provided after the moving instruction "mov" in step 2 subsequent to an IF part in step 1 compares and judges whether the content of a register r3 is equal to or larger than 0 or not, namely,
register r3.gtoreq.0. PA1 I. a detecting step of detecting an instruction sequence including a branch instruction from an instruction sequence which can be executed by the pipeline computer: and PA1 II. a converting step of converting the instruction sequence including the branch instruction detected in the detecting step I into the equivalent instruction sequence including no branch instruction.
When the above comparison condition is satisfied, there is no branch (hereinafter, a state in which the processing routine is not branched is also referred to as "branch is not taken"), so that a branch instruction "ble L1" is skipped and instructions in steps 4 and 5 as a THEN part are sequentially executed in accordance with the order. On the other hand, when the condition of the comparing instruction is not satisfied (r3&lt;0) in step 3, there is a branch (hereinafter, a state in which the processing routine is branched is also referred to as "branch is taken"). The processing routine is branched to a label L1 shown by the branch instruction "ble L1" and an operating instruction "add" is executed in step 6.
However, hitherto, the existence of the branch instruction in the program becomes a cause of deterioration of the performance of a pipeline computer. For example, in the program of the IF.about.THEN type in FIG. 1, THEN parts in instruction steps 4 and 5 are executed or are not executed in accordance with the result of the comparing instruction in step 3. Therefore, the conventional pipeline computer copes with such a program including the branch instruction as follows.
First, an assumption such that "all of the branch instructions are not branched" is made. For this purpose, even if a branch instruction appears, an instruction fetch is continued while ignoring such a branch instruction and the instructions are sequentially executed in accordance with the order. For instance, the pipeline computer has a construction of four stages: a fetch stage F; a first execution stage E1; a second execution stage E2; and a write stage W. Therefore, in each cycle, the instructions are sequentially fetched to the stage F and, at the same time, the precedent instructions are moved to the stages E1, E2, and W. Therefore, in the case where the comparison condition is satisfied and there is no branch (not taken), it is sufficient to continue the instruction execution cycle of the pipeline computer, so that an overhead doesn't occur. However, in the case where the comparison condition is not satisfied and there is a branch (taken), the instruction such that the processing stage has been progressed on the assumption that the processing routine is not branched must be cancelled. It takes a time to execute processes by a time corresponding to such a cancelling operation. It also takes a time to fetch the instruction on the branch destination side and there is a problem such that the overhead increases.
A method of predicting whether the branch instruction is branched or not is also considered as another method. It is, however, generally difficult to perfectly predict whether the branch instruction is taken or not, so that an overhead of the branch certainly occurs. Particularly, in a parallel machine at an instruction level such as VLIW (Very Long Instruction Words) or superscalar, there is a tendency such that the overhead due to the branch instruction further increases.